package com.atguigu.linklist;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class MergeKList {
    public static void main(String[] args) {
        ListNode head1=new ListNode(1);
        head1.next=new ListNode(2);
        head1.next.next=new ListNode(3);
        ListNode head2=new ListNode(4);
        head2.next=new ListNode(5);
        head2.next.next=new ListNode(6);
        head2.next.next.next=new ListNode(7);
        ArrayList<ListNode> list=new ArrayList<>();
        list.add(head1);
        list.add(head2);
        ListNode cur=mergeKLists(list);
        while(cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }
    }
    public static ListNode mergeKLists(ArrayList<ListNode> lists){
        PriorityQueue<ListNode> queue=new PriorityQueue<>((o1,o2)->{
            return o1.val-o2.val;
        });
        //将k个链表的头结点都添加到小顶堆中（如果不为空)
        for(int i=0;i<lists.size();i++){
            ListNode cur=lists.get(i);
            if(cur!=null) {
                queue.add(cur);
            }
        }
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        while(!queue.isEmpty()){
            ListNode tmp=queue.poll();
            cur.next=tmp;
            cur=cur.next;
            if(tmp.next!=null){
                queue.add(tmp.next);
            }
        }
        return res.next;
    }
}
